package chapter4;

/**
 * 斐波那契数列问题的递归和动态规划
 * 1 1 2 3 5 8 13 ...(第1项，第2项为1，。。。)
 */
public class Fibonacci {

    /**
     * 递归方法
     * 复杂度O(2^N)
     * @param n
     * @return
     */
    public int f1(int n) {
        if (n < 1) return 0;
        if (n == 1 || n == 2) return 1;
        return f1(n - 1) + f1(n - 2);
    }

    /**
     * 迭代方法
     * 复杂度O(n)
     * @param n
     * @return
     */
    public int f2(int n) {
        if (n < 1) return 0;
        if (n == 1 || n == 2) return 1;
        int res = 1;
        int pre = 1;
        int temp = 0;
        for(int i = 3; i <= n; i++) {
            temp = res;
            res = res + pre;
            pre =temp;
        }
        return res;
    }

    /**
     * 矩阵乘法的动态规划算法
     * 复杂度O(logN)
     * F(n)=F(n-1)+F(n-2),是一个二阶递推数列，可以用矩阵乘法的形式表示
     * (F(n),F(n-1))=(F(n-1),F(n-2))*((a,b),(c,d)) =>
     * (F(n),F(n-1))=(1,1)*((1,1),(1,0))^(n-2)
     * 求解矩阵的n次方，可以参考求解整数的n次方的O(logN)的方法
     * @param n
     * @return
     */
    public int f3(int n) {
        if (n < 1) return 0;
        if (n == 1 || n == 2) return 1;
        int[][] base = {{1,1},{1,0}};
        int[][] res = matrixPower(base,n - 2);
        return res[0][0] + res[1][0];
    }

    /**
     * 求整数的次方
     * x^n 将n写成二进制形式，如 10^75, 75的二进制为1001011
     * 10^75 = 10^64 * 10^8 * 10^2 * 10^1
     * 复杂度 O(logN)
     * @param x
     * @param n
     * @return x^n
     */
    public static int fn(int x, int n) {
        int res = 1;
        int temp = x;
        for (; n != 0 ; n >>= 1) {
            if((n & 1) != 0) {
                res = res * temp;
            }
            temp = temp * temp;// x^2 -> x^4 -> x^8 -> x^16 -> x^32 -> ...
        }
        return res;
    }
    // 朴素算法的分治法 n>=0
    public static int cube(int x, int n) {
        int returnData = -1;
        if (n == 0 && x != 0) return 1;
        if (n == 1) {
            returnData = x;
        } else if (n > 1) {
            int m = n / 2;
            int s = cube(x, m);
            if (n % 2 == 0) {
                returnData = s * s;
            } else {
                returnData = x * s * s;
            }
        }
        return returnData;
    }

    /**
     * 矩阵的N次方
     * @param m
     * @param n
     * @return m^n
     */
    public static int[][] matrixPower(int[][] m, int n) {
        int[][] res = new int[m.length][m[0].length];
        for (int i = 0; i < res.length; i++) {
            res[i][i] = 1;
        }
        int[][] temp = m;
        for (; n != 0; n >>= 1) {
            if ((n & 1) != 0) {
                res = muliMatrix(res, temp);
            }
            temp = muliMatrix(temp, temp);
        }
        return res;
    }

    /**
     * 两矩阵相乘
     * @param m1
     * @param m2
     * @return m1*m2
     */
    public static int[][] muliMatrix(int[][] m1, int[][] m2) {
        int[][] res = new int[m1.length][m2[0].length];
        for (int i = 0; i < m2[0].length; i++) {
            for (int j = 0; j < m1.length; j++) {
                for (int k = 0; k < m2.length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }
}
